class Solution {
public:
    static const int N=1e5+10;

    int son[N][26];
    int idx;
    int cnt[N];
    void init(vector<string>& dictionary)
    {
        for(int i=0;i<dictionary.size();i++)
        {
            insert(dictionary[i]);
        }
    }
    void insert(string& t)
    {
        int p=0;
        for(int i=0;i<t.size();i++)
        {
            int k=t[i]-'a';
            if(!son[p][k])
            {
                son[p][k]=++idx;
                p=son[p][k];
            }
            else{
                p=son[p][k];
            }
        }
        cnt[p]+=1;
    }
    string query(string& t)
    {
        string ret;
        int p=0;
        for(int i=0;i<t.size();i++)
        {
            int k=t[i]-'a';
            if(son[p][k])
            {
                ret+=t[i];
                p=son[p][k];
            }
            else break;
            if(cnt[p])
                return ret;
        }
        return cnt[p]?ret:t;
    }
    string replaceWords(vector<string>& dictionary, string sentence) {
        memset(son,0,sizeof(son));
        idx=0;
        string ret;
        init(dictionary);
        vector<string> v;
        stringstream ss(sentence);
        string t;
        while(ss>>t)
        {
            // cout<<t<<' '<<query(t)<<endl;
            v.push_back(query(t));
        }
        for(int i=0;i<v.size();i++)
        {
            if(i)
            {
                ret+=' '+v[i];
            }
            else{
                ret+=v[i];
            }
        }
        return ret;
    }
};
